1. Field of the Invention
The present invention relates to a system for detecting errors in digital data transmission and, more particularly, to a system for verifying that the mechanism for detecting errors itself operates properly.
In any digital system in which data is transmitted from one device or functional unit to another, one or more of the data bits in each data word or message may be received in error. This has been a problem since digital data processing systems have existed.
As more sophisticated data processing operations are performed, requiring the use of more complex equipment, there is a greater need for systems to detect and correct errors in data transfer. For example, operations such as merging of files, sorting of data within files, transmission of data to and from remote locations by means of radio broadcast, cables, fiber optics and the like, numerical/statistical analyses, complex data handling procedures and word processing operations require increased reliability in data transfer. In the field of telecommunications and telemetry especially, error rates tend to increase when data is transmitted over analog lines at high baud rates. If data errors occur but are undetected, valuable information and system operation itself may be affected. Thus, error detecting and/or correcting features are not only advantageous for sophisticated systems, they are indispensable to guarantee system integrity.
Systems have been developed to detect errors generated during data transfer. One of the earliest methods for detecting errors was the parity check code. A binary code word has odd parity if an odd number of its digits are 1's. For example, the number 1011 has three 1 digits and therefore has odd parity. Similarly, the binary code word 1100 has an even number of 1 digits and therefore has even parity.
A single parity check code is characterized by an additional check bit that is added to each word to generate either odd or even parity. An error in a single digit or bit in a data word is discernible since the parity check bit associated with that data word is reversed from what is expected. Typically, a parity generator adds the parity check bit to each word before transmission. This technique is called padding the data word. Conventionally, at the receiving functional unit or receiver, the digits in the word are tested. If the parity is incorrect, one of the bits in the data word is considered to be in error. When an error is detected at a receiver, a request for repeat transmission can be given so that the error can be corrected. Only errors in an odd number of digits can be detected with a single parity check, since an even number of errors results in the parity expected for a correct transmission. Moreover, the specific bit in error cannot be identified by the parity check procedure as hereinabove described.
A more sophisticated error detection system was later devised. Data words of a fixed length of bits can be grouped into blocks of a fixed number of data words each. Parity checks can then be performed between different data words as well as for each individual data word. A block parity code can detect many patterns of errors and can be used not only for error detection, but also for error correction when an isolated error occurs in a given row and column of a matrix. While geometric codes are an improvement over parity check bits per se, they still cannot be used to detect errors that are even in number and symmetrical in two dimensions.
After parity check codes and geometric codes were devised, a code was invented by Hamming, after whom it is named. The Hamming code is a system of multiple parity checks that encodes data words in a logical manner so that single errors can be not only detected but also identified for correction. A transmitted data word used in the Hamming code consists of the original data word and parity check digits appended thereto. Each of the required parity checks is performed upon specific bit positions of the transmitted word. The system enables the isolation of an erroneous digit, whether it is in one of the original data word bits or in one of the added parity check bits.
If all the parity check operations are performed successfully, the data word is assumed to be error free. If one or more of the check operations is unsuccessful, however, a single bit error is uniquely determined by decoding so-called syndrome bits, which are derived from the parity check bits.
The Hamming code is only one of a number of codes generically called error correcting codes (ECC's). Codes are usually described in mathematics as closed sets of values that comprise all the allowed number sequences in the code. In data communications, transmitted numbers are essentially random data patterns which are not related to any predetermined code set. The sequence of data, then, is forced into compliance with the code set by adding to it at the transmitter, as hereinabove mentioned. A scheme has heretofore been developed to determine the precise string to append to the original data stream to make the concatenation of transmitted data a valid code. There is a consistent way of extracting the original data from the code value at the receiver and to deliver the actual data to the location where it is ultimately use. For the code scheme to be effective, it must contain allowed values sufficiently different from one another so that expected errors do not alter an allowed value in such a manner that it becomes a different allowed value of the code.
A cyclic redundancy check (CRC) code consists of strings of binary data which, combined with the transmitted data, is evenly divisible by a generator polynomial. The CRC code is a number selected to result in a set of values different enough from one another to achieve a low probability of an undetected error. To determine what to append to the string of original data, the original string is divided as it is being transmitted. When the last data bit is passed, the remainder from the division is the required string that is added since the string including the remainder is evenly divisible by the generator polynomial. Because the generator polynomial is of a known length, the remainder added to the original string is also of fixed length.
At the receiver, the incoming string is divided by the generator polynomial. If the incoming string does not divide evenly, an error is assumed to have occurred. If the incoming string is divided by the generator polynomial evenly, the data delivered to the ultimate destination is the incoming data stripped of the fixed length remainder field.
A longitudinal redundancy code (LRC) is a special case of CRC in which the particular generator polynomial chosen results in the same CRC code as would be obtained by performing an EXCLUSIVE OR operation once for every bit in the data word. If the data stream were represented as a succession of multi-bit words, for example, the LRC code added to the end of the stream would equal the first word EXCLUSIVE ORed with the second, EXCLUSIVE ORed with the third, and so on. When the check is made at the receiver, the result is zero if no errors occurred. This is simply because the EXCLUSIVE OR of any value with itself is zero.
From the foregoing discussion it can be seen that solutions to the problem of erroneous data transmission have conventionally dealt with the symptom rather than the cause. That is, when data is received and determined to be erroneous, the assumption has heretofore been that it is the data that is incorrect. The solution has been to retransmit or modify the data, often using the very same error detection techniques.
If the checking code generator is faulty, however, the same checking code may be generated for the same data message. At best, no progress in finding a remedy for the error is made. Worse, intermittent and unpredictable errors can be generated. Accordingly, the same or other malfunctions are likely to occur. In fact, the most insidious circumstance is one in which data is received erroneously but the checking code indicates the contrary. When this situation occurs, the receiving functional unit and the system connected thereto treat the data as if it were accurate, resulting in potentially serious consequences downstream.
U.S. Pat. No. 4,454,600 issued to LeGresley teaches the use of a circuit for generating CRC codes. It is cited herein as an example of many types of CRC generator circuits currently used.
U.S. Pat. No. 4,520,481 issued to Israel teaches the use of a CRC circuit for detecting malfunctioning units.
U.S. Pat. No. 4,312,068 issued to Goss et al teaches a method of comparing CRC codes that are generated both by the transmitter and by the receiver to ensure proper data transmission.
U.S. Pat. No. 4,422,067 issued to Clark et al discloses a cyclic redundancy checker that ceases to function upon certain conditions, thereby causing an associated circuit to de-energize a load in a control system.
U.S. Pat. No. 3,889,109 issued to Blessin teaches the use of a testing mechanism to verify operation of send control logic and receive control logic. During testing operations, a communications subchannel is configured in a so-called wraparound mode so that data sent from a processor is routed through the send control logic and the receive control logic back to the processor. A CRC check is performed on the return data to determine if errors are present. If so, the send control logic and the receive control logic can be selectively bypassed to aid in determining where the error originated.
Each of the aforementioned systems can detect an error not due to a defect in data, but due to a defect in the checking code appended thereto. Moreover, an error in data may occur but, due to a defect in the appended checking code, the error may not be detected by any of these systems. Such a situation can occur if the checking code generator malfunctions or is defective.
It would be advantageous to provide a system for ensuring correct data transmission between two functional units.
It would also be advantageous to provide a system for ensuring that checking codes themselves are generated properly.
It would also be advantageous to provide a system for verifying proper operation of a checking code generator by the exercise thereof.
It would further be advantageous to provide a system for exercising checking code generators at either or both ends of a transmission link.
It would also be advantageous to provide a system whereby a comparator is used to compare checking codes generated by each of the devices in communicative relationship with one another.
It would further be advantageous to provide a system for indicating whether a checking code generator is operating properly.